/*
 * @Author: szx
 * @Date: 2022-02-11 12:59:12
 * @LastEditTime: 2022-02-11 14:20:19
 * @Description:
 * @FilePath: \leetcode\900-999\912\912_heap_sort.js
 */

function heapify(arr, i, len) {
    // 堆调整
    // 2i+1是左节点，2i+2是右节点，最大值的下标为当前节点
    const left = 2 * i + 1,
        right = 2 * i + 2;
    let largest = i;

    // 判断子节点是否存在，并找出最大的那个
    if (left < len && arr[left] > arr[largest]) largest = left;
    if (right < len && arr[right] > arr[largest]) largest = right;

    // 如果最大值不等于父节点（就是子节点比父节点大），那么就进行交换，并进行
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest, len);
    }
}

function sortArray(nums) {
    // 先初始化，建立大顶堆
    let len = nums.length;
    for (let i = Math.floor(len / 2); i >= 0; i--) {
        heapify(nums, i, len);
    }
    for (let i = nums.length - 1; i > 0; i--) {
        // 交换根节点和末尾节点
        swap(nums, 0, i);
        len--;
        heapify(nums, 0, len);
    }
    return nums;
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// console.log(sortArray([4, 5, 2, 1, 3]));
console.log(sortArray([-7, -5, 4, 0, -4, -1, 0, -1, 7, 9]));
